# Principal Component Analysis (PCA) Implementation (medium)
import numpy as np

# 从头开始执行主成分分析（PCA）的 Python 函数。
# 该函数应接受一个二维 NumPy 数组作为输入，其中每行代表一个数据样本，每列代表一个特征。
# 该函数应标准化数据集，计算协方差矩阵，找到特征值和特征向量，
# 并返回主成分（对应于最大特征值的特征向量）。
# 该函数还应接受一个整数 k 作为输入，表示要返回的主成分的数量。

def pca(data: np.ndarray, k: int) -> list[list[int | float]]:
    # 标准化数据集
    data_mean = np.mean(data, axis=0)
    data_std = np.std(data, axis=0)
    standardized_data = (data - data_mean) / data_std

    # 计算协方差矩阵
    covariance_matrix = np.cov(standardized_data, rowvar=False)

    # 计算特征值和特征向量
    eigenvalues, eigenvectors = np.linalg.eigh(covariance_matrix)

    # 按特征值从大到小排序特征向量
    sorted_indices = np.argsort(eigenvalues)[::-1]
    sorted_eigenvectors = eigenvectors[:, sorted_indices]

    # 选择前 k 个主成分
    principal_components = np.round(sorted_eigenvectors[:, :k], 4)

    return principal_components.tolist()

def pca(data, k):
    # Standardize the data
    data_standardized = (data - np.mean(data, axis=0)) / np.std(data, axis=0)
    
    # Compute the covariance matrix
    covariance_matrix = np.cov(data_standardized, rowvar=False)
    
    # Eigen decomposition
    eigenvalues, eigenvectors = np.linalg.eig(covariance_matrix)
    
    # Sort the eigenvectors by decreasing eigenvalues
    idx = np.argsort(eigenvalues)[::-1]
    eigenvalues_sorted = eigenvalues[idx]
    eigenvectors_sorted = eigenvectors[:,idx]
    
    # Select the top k eigenvectors (principal components)
    principal_components = eigenvectors_sorted[:, :k]
    
    return np.round(principal_components, 4).tolist()